/**
 * @brief 3.4.2 迭代器运算
 * @param argc
 * @param argv
 * @return int
 */
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using std::cin, std::cout, std::endl;
using std::iterator;
using std::string;
using std::vector;
int main(int argc, char const *argv[])
{
    // 计算得到最接近vi中间元素的一个迭代器
    vector<int> vi{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto mid = vi.begin() + vi.size() / 2; // 迭代器所指示元素为vi[5]
    cout << *mid << endl;

    // 使用迭代器完成二分搜索
    vector<string> text{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n",
                        "o", "p", "q", "r", "s", "t", "w", "v", "u", "x", "y", "z"}; // text必须是有序的
    auto beg = text.begin(), end = text.end();
    auto midi = text.begin() + (end - beg) / 2; // 初始状态下的中间点
    string sought;
    cin >> sought;
    while (midi != end && *midi != sought)
    {
        if(sought < (*midi)) // 我们要找到的元素在前半部分吗
            end = midi; // 忽略后半部分
        else
            beg = midi;  // 忽略前半部分
        midi = beg + (end-beg)/2; // 新的中间点
    }
    if(midi == end) // 循环过程终止时，mid或者等于end或者指向要找的元素
        cout << "There are no element in the sequence:" << sought << endl;
    else
        cout << "The element that you are looking for is in the sequence" << endl;

    return 0;
}
